package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 6. Z字形变换
 *将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
 *
 * 比如输入字符串为 "LEETCODEISHIRING"行数为 3 时，排列如下：
 *
 * L   C   I   R
 * E T O E S I I G
 * E   D   H   N
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
 *
 * 请你实现这个将字符串进行指定行数变换的函数：
 *
 * string convert(string s, int numRows);
 * 示例 1:
 *
 * 输入: s = "LEETCODEISHIRING", numRows = 3
 * 输出: "LCIRETOESIIGEDHN"
 * */
public class Zconvert {
    //方法1： 从上往下 逐行读取 时间复杂度：O(n) 空间复杂度: O(n)
    public String convert(String s,int numRows){
        List<StringBuilder> rows = new ArrayList<>();
        if (numRows == 1){
            return s;
        }

        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }

        /**
         * @Variable curRow 当前行号
         * @Variable goDown 当前访问方向 true：向下 false： 向上
         * 从上往下读取每一行 到了底部再往上读取
         * */
        int curRow = 0;
        boolean goDown = false;

        for (char c : s.toCharArray()){
            rows.get(curRow).append(c);
            if(curRow == 0 || curRow == numRows-1){
                goDown = !goDown;
            }
            curRow += goDown ? 1 : -1;

        }
        String result = "";
        for (StringBuilder stringBuilder : rows){
            result += stringBuilder.toString();
        }

        return result;
    }


    // 方法二：按行访问 时间复杂度和空间复杂度为 O(n)
    /**
     * 找下标规则：具体方法一下链接
     * https://leetcode-cn.com/problems/zigzag-conversion/solution/6-z-zi-xing-bian-huan-c-c-by-bian-bian-xiong/
     *
     * */
    public String convert1(String s,int numRows) {
        if (numRows <= 1){
            return s;
        }
        int len = s.length();
        int convert = numRows*2 - 2;
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j+i < len; j += convert) {
                ret.append(s.charAt(i+j));
                if(i != 0 && i != numRows - 1 && j + convert - i < len){
                    ret.append(s.charAt(j + convert - i));
                }
            }
        }

        return ret.toString();
    }


    // main
    /**
     * 这道题没有太大的难度,但是我想了一下午 最后还是参照的大佬的代码明白了这一题
     * 其实最主要的还是思维 和 找规则
     * 之前我企图找规则 但是我没有想到用下标去找规则，我是找每个字母的间隔数量是多少
     * 所以有的时候找规则 尽量用下标去尝试
     * 反向思维也是非常重要的
     *
     * */
    public static void main(String[] args) {
        Zconvert z = new Zconvert();
        String s = z.convert1("LEETCODEISHIRING" , 3);
        System.out.print(s);
    }
}
